A mode of operation, or mode, for short, is an algorithm that implements a symmetric key block cipher algorithm to provide an information service, such as confidentiality or authentication. With the advent of new block ciphers, such as the Advanced Encryption Standard (AES), there is a need to update long-standing modes of operation and an opportunity to consider the development of new modes such as a combined mode for authentication and confidentiality (commonly referred to as “authenticated encryption” or “integrity-aware encryption”).
The notion of a high-speed encryption mode that also provides authentication, i.e., a means for determining the integrity of the encrypted data, has been pervasive in the security industry for the last several years. A plenitude of false-starts in this area had originally been quite discouraging. For example, the National Security Agency (NSA), purportedly the world's premier cryptographic research organization, had to retract their “Dual Counter Mode” proposal to the National Institute of Standards and Technology (NIST), when fatal security flaws were found in its design. See, for example, Donescu et al., “A Note on NSA's Dual Counter Mode of Encryption,” (Aug. 5, 2001), the disclosure of which is incorporated herein by reference in its entirety.
The motivations for a high-speed “integrity-aware” encryption mode is readily apparent—as data links move into the multi-gigabit realm, cryptographic protection functions based on conventional cipher modes cannot be made to run at high data rates, even on custom-built hardware. What is needed then is a mode that is arbitrarily parallelizable, i.e., block cipher operations can be executed in an architecture independent parallel or pipelined manner, thereby allowing throughput to be defined not on the speed of an individual work unit, but on the degree to which parallelism matches the offered load. A mode that is arbitrarily parallelizable implies that the overhead of the confidentiality and authentication mechanisms is incurred only once for the entire plaintext data set regardless of how many processing units are used in parallel.
Conventional techniques to provide both data confidentiality and authentication using only a single processing pass over the plaintext typically employ different variations of the Cipher Block Chaining (CBC) mode of encryption. In CBC mode, the plaintext undergoes an exclusive-or (“XOR” or ⊕ in mathematical notation) operation with the previous ciphertext block before it is encrypted. After a plaintext block is encrypted, the resulting ciphertext is also stored in a feedback register. Before the next plaintext block is encrypted, it is XORed with the feedback register to become the next input to the encrypting routine. Therefore, each ciphertext block is dependent not just on the plaintext block that generated it but on all the previous plaintext blocks. Accordingly, CBC encryption is not parallelizable.
A very common approach for making an authentication tag from a block cipher is the cipher block chaining message authentication code (CBC MAC). In a CBC MAC algorithm, a message is partitioned into n-bit blocks. For each input message block, the algorithm enciphers the result of the input with the previous output block. The result of the final enciphering is the authentication tag. Such a technique is not parallelizable as it suffers from its inherent block-to-block serial dependency. It is this serial dependency that frustrates CBC-based attempts to provide multi-gigabit authentication tags at the speed at which an advanced circuit or communications line can transfer information.
United States Patent Application Publication Nos. 2001/0046292 and 2001/0033656 to Gligor et al., the disclosures of which are both incorporated herein by reference in their entirety, present a block encryption mode referred to as eXtended Ciphertext Block Chaining (XCBC) that purportedly provides both data confidentiality and integrity in a parallelizable fashion. See also United States Patent Application Publication No. 2002/0048364 to Gligor et al., the disclosure of which is incorporated herein by reference in its entirety. XCBC employs a single cryptographic primitive and a single processing pass over the input plaintext string by using a non-cryptographic Manipulation Detection Code (MDC) function. Unfortunately, XCBC suffers from the same drawbacks as with CBC MAC, i.e., the inherent serial nature of the block chaining that prohibits architecture-independent parallel and pipelined operation efficiently at the level of individual block processing.
The first apparently correct construction of a block encryption mode that provides both data confidentiality and integrity was the Integrity Aware Parallelizable Mode (IAPM) designed by Jutla. See, for example, United States Patent Application Publication No. 2003/0152219 to Coppersmith et al., the disclosure of which is incorporated herein by reference in its entirety. IAPM relies on a pseudorandom function based on a Gray code, i.e., cyclic binary code, which is applied to the blocks of a message during processing. The overall scheme provides confidentiality and integrity at a small increment to the cost of providing confidentiality alone. Nonetheless, the use of a simple Gray code gives cryptographers a sense of unease about the underlying security.
Rogaway later modified the IAPM construction in what is referred to as an “Offset Codebook” (OCB) mode. See United States Patent Application Publication Nos. 2002/0051537 and 2002/0071552 to Rogaway, the disclosures of which are both incorporated herein by reference in their entirety. OCB retains the principal characteristics of IAPM by employing a parallelizable variable-input-length pseudorandom function constructed out of a Gray code to provide a message authentication code.
In view of the foregoing, it would be desirable to provide a parallelizable integrity-aware encryption technique that overcomes the deficiencies and drawbacks of the prior art.